def calc_distance1(str1, str2):
    dp= [[x for x in range(len(str1)+1)] for y in range(len(str2)+1)]
    for j in range(1, len(str2)+1):
        dp[j][0] = dp[j-1][0]+1
    for i in range(1,len(str1)+1):
        for j in range(1,len(str2)+1):
            if str1[i-1] == str2[j-1]:
                dp[j][i] = dp[j-1][i-1]
            else:
                de=dp[j-1][i-1]+1
                add=dp[j-1][i]+1
                re=dp[j][i-1]+1
                dp[j][i]=min(de,add,re)
    for i in range(1,len(str1)+1):
        for j in range(1,len(str2)+1):
            print(str(i) + "_" + str(j), dp[i][j])


mem = {}
def calc_distance(str1, str2):
    if len(str1) == 0:
        return len(str2)
    if len(str2) == 0:
        return len(str1)
    if str(len(str1)) + "_" + str(len(str2)) in mem:
        return mem[str(len(str1)) + "_" + str(len(str2))]
    if str1[-1] == str2[-1]:
        return calc_distance(str1[:len(str1)-1], str2[:len(str2)-1])
    aa = calc_distance(str1[:len(str1)-1], str2)
    bb = calc_distance(str1, str2[:len(str2)-1])
    cc = calc_distance(str1[:len(str1)-1], str2[:len(str2)-1])
    ret = min(aa, bb, cc) + 1
    mem[str(len(str1)) + "_" + str(len(str2))] = ret
    return ret


if __name__ == '__main__':
    """
    abcdefg
abcdef
abcde
abcdf
abcde
bcdef
"""
    a = calc_distance("abcde","bcdef")
    print(a)
    print(mem)
    ### 多次循环要清空mem